package 二零年8月;

import java.net.DatagramPacket;
import java.util.Map;

/*      剪绳子问题
*   给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
* 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
*
* 思路：把题目剖析，其实就是数字n拆解为基因子的最大乘积。 总之，看到求最大值的问题，优先想到动态规划。
* 有两种做法，比较简单的关系推导就是从n=1开始找规律，划到10时就可以得出规律，在n>6时就可以得出，dp(n)=dp(n-3)*3; 但是这种做法不符合动态规划的
* 求解思路，所以用下面推导公式的的思路。
*
*   可以使用动态规划，逐步分析当前n是否与n-1对应的值有关系
*   设一维数组 dp[n]来代表存储的值，
*   首先来判断f（n）, 根据划分，f(n)=max{i*f(n-i)},i=1,2...,n-1         例如：f(3)=1*f(3-1) || 2*f(3-2) , 取其中的最大值
*   显然，上述表达式的f(n-i)还需要再次分解，但如果n-i比f(n-i)要大，显然就不需要分解了，直接得出以下公式
*   f(n)=max{i*f(n-i),i*(n-i)},i=1,2...,n-1
*
*   初始化： n=2=1+1 ，dp[2]=1
 *
* */
public class S14_1 {
    public int cuttingRope(int n) {
        if(n<2){
            return 0;
        }
        int []dp=new int[n+1];
        dp[0]=0;
        dp[1]=0;
        dp[2]=1;
        for (int i = 3; i <=n ; i++) {
            for (int j = 1; j <i ; j++) { //第二层循环是为了找出当前i的所有排列组合的最大乘积
                dp[i]= Math.max(Math.max(j*dp[i-j],j*(i-j)),dp[i]);
            }
        }
        return dp[n];
    }
}
